package com.ting.test.algorithms.stack;

import java.util.Stack;

/**
 * Created by 雷霆 on 2020/3/13.
 * <p>
 * Description：
 *
 设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。

 push(x) -- 将元素 x 推入栈中。
 pop() -- 删除栈顶的元素。
 top() -- 获取栈顶元素。
 getMin() -- 检索栈中的最小元素。
 示例:

 MinStack minStack = new MinStack();
 minStack.push(-2);
 minStack.push(0);
 minStack.push(-3);
 minStack.getMin();   --> 返回 -3.
 minStack.pop();
 minStack.top();      --> 返回 0.
 minStack.getMin();   --> 返回 -2.
 */
public class MinStack {
    private Stack<Integer> stack = null;
    private Stack<Integer> helpStack = null;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        stack = new Stack<Integer>();
        helpStack = new Stack<Integer>();
    }

    public void push(int x) {
        stack.push(x);
        if (helpStack.isEmpty() || helpStack.peek() > x) {
            helpStack.push(x);
        } else {
            helpStack.push(helpStack.peek());
        }

    }

    public void pop() {
        if (!stack.isEmpty()) {
            stack.pop();
            helpStack.pop();
        }
    }


    public int top() {
        if (!stack.isEmpty()) {
            return stack.peek();

        }
        throw new RuntimeException("栈为空!");
    }

    public int getMin() {
        if (!helpStack.isEmpty()) {
            return helpStack.peek();
        }
        throw new RuntimeException("栈为空!");
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */